1. Field of the Invention
The present invention is directed generally to Markov chain Monte Carlo simulations and, more particularly, to a practical method of obtaining regeneration in a Markov chain.
2. Description of the Background
In statistics, answers to questions are often obtained by constructing statistical models of real-life situations and then analyzing the various probabilities of certain events occurring in the models. Such techniques can be used to determine the probability (based on collected data), for instance, that it will rain tomorrow, that a share price will exceed $20 with the next few months, or that there is racial bias in a company's hiring policies.
Of course, the validity of the analysis then relies quite heavily on the quality of the statistical model (i.e. on how well it approximates reality). In the past, statisticians have been inclined to “bend” reality to fit a specific group of models that they could work with. However, with the advent of Markov chain Monte Carlo (MCMC) methods, this is no longer necessary. MCMC methods allow statisticians to work with extremely complicated models. This means that statisticians can choose much more realistic models for analysis than they have previously.
There are some drawbacks, however. MCMC methods are computationally intensive, relying on simulation of large numbers of “possible outcomes.” Furthermore, although the precision of answers to questions increases as the MCMC continues to generate simulations, it is difficult to compute this precision once the MCMC run is finished. Another drawback is the burn-in problem, that is, uncertainty about how long it takes before the chain is (by some measure) sufficiently close to its limiting distribution. Another drawback is the inherent correlation between successive elements of the chain. This correlation makes it difficult to estimate the variance of the Monte Carlo estimates.
Regeneration in MCMC is a tool which enables statisticians to avoid the burn-in problem and to determine relatively accurately the precision of estimates at the end of the MCMC run. Essentially, regeneration mitigates two of the major problems with MCMC methods. In addition, it provides a very convenient means of using parallel-processors to construct a single MCMC run. (In the past, people have used parallel processors to generate lots of short MCMC runs instead of one long one, but others have argued that one long run is better than multiple short runs.)
Early work on regenerative simulation can be found in M. A. Crane and D. L. Iglehart, Simulating Stable Stochastic Systems, I: General multi-server queues, Journal of the Association of Computing Machinery, 21:103–113, 1975, M. A. Crane and D. L. Iglehart, Simulating stable stochastic systems, II: Markov chains, Journal of the Association of Computing Machinery, 21:114–123, 1975 and M. A. Crane and A. J. Lemoine, An Introduction to the Regenerative Method for Simulation Analysis, volume 4 of Lecture Notes in Control and Information Sciences, Springer, 1977, while more recent discussion can be found in B. D. Ripley, Stochastic Simulation, Wiley, 1987 and P. Mykland, L. Tierney, and B. Yu, Regeneration in Markov chain samplers, Journal of the American Statistical Association, 90:233–241, 1995. Loosely speaking, a regenerative process “starts again” probabilistically at each of a set of random regeneration points, called regeneration points. Furthermore, conditioned on any regenerative point, the future of the process is independent of the past. (Probably the simplest example of a set of regeneration points is the set of hitting times of some arbitrary fixed state. However, this example is not very interesting for most continuous state-space chains, because the expected time between such regeneration points can be infinite.)
If regeneration points can be identified in the Markov chain, then tours of the chain between these times are (on an appropriate probability space) independent, identically distributed (i.i.d.) entities. Thus, if a fixed number of tours is generated, it makes no sense to discard any initial tours, or indeed, any part of the first tour, because properties of the “clipped” tour would be quite different from properties of the other un-clipped tours. In this sense, the problem of burn-in is avoided. In addition, because the tours are i.i.d, when estimating the expectation of an arbitrary function of a parameter, the variance of the estimator itself can be estimated. There are further benefits as well. In constructing a regenerative chain, it is not necessary for all the tours to be generated on a single processor, and it is therefore possible to use parallel processors to generate a single long chain with the desired target distribution.
Previous methods of using regeneration in MCMC simulation have been limited by the complexity of their implementation. Hence they are not used much in practice. Thus, the need exists for a method of identifying regeneration points that is practical and simple to implement.